import random
import _00SetFunc as ss

#在笛卡尔积中，随机产生n个元素的关系
def createrelation(X,Y,n):
    global XY,R
    XY=ss.Cartesianproduct(X,Y)
    R=random.sample(list(XY),n)
    return set(R)

#对任意集合X，求恒等关系Ix(X,X)
def Ixset(X):
    Ix=set({})
    for x in X:
        Ix.add((x,x))
    return Ix

#对任意集合X，求恒等关系Ux(x,y)
def Uxset(X):
    Ux=set({})
    for x in X:
        for y in X:
            Ux.add((x,y))
    return Ux

#复合运算
def composite(R,S):
    RS=set({})
    for (x,y) in R:
        for (u,v) in S:
            if(y==u):
                RS.add((x,v))
    return RS

#逆运算
def inverse(R):
    Rv=set({})
    for (x,y) in R:
        Rv.add((y,x))
    return Rv

#指数运算
def power(Rn,R):
    Rn1=set({})
    for (x,y) in Rn:
        for (u,v) in R:
            if(y==u):
                Rn1.add((x,v))
    return Rn1

def powern(R,n):
    Rn=R
    for k in range(2,n+1):
        Rn=power(Rn,R)
    return Rn

#关系自反性判断
def isreflexive(X,R):
    tv=True
    for x in X:
        p=(x in X)
        q=((x,x)in R)
        tv= tv and (not p or q)
    return tv

#反自反性判断
def isirreflexive(X,R):
    tv=True
    for x in X:
        p=(x in X)
        q=(not((x,x)in R))
        tv= tv and(not p or q)
    return tv

#关系对称性判断
def issymmetric(X,R):
    tv=True
    for x in X:
        for y in X:
            p=((x,y)in R)
            q=((y,x)in R)
            tv= tv and (not p or q)
    return tv

#关系反对称判断
def isantisymmetric(X,R):
    tv=True
    for x in X:
        for y in X:
            p=((x,y)in R) and((y,x)in R)
            q=(x==y)
            tv=tv and (not p or q)
    return tv

#判断关系传递性
def istransitive(X,R):
    tv=True
    for x in X:
        for y in X:
            for z in X:
                p=((x,y)in R) and((y,z) in R)
                q=((x,z) in R)
                tv= tv and((not p)or q)
    return tv

#RUIx是自反关系
def reflexiverelation(X,R):
    Ix=Ixset(X)
    R=set(R)|set(Ix)
    return R

#R-Ix反自反关系
def irreflexiverelation(X,R):
    Ix=Ixset(X)
    R=set(R)-set(Ix)
    return R

#RUR'对称关系
def symmetricrelation(X,R):
    Ix=Ixset(X)
    Rv=set(inverse(R))
    R=set(R)
    R=(R|Rv)
    return R

#（R-Rn*R-1))U（Rn*Ix）是反对称关系
def antisymmetricrelation(X,R):
    Ix=Ixset(X)
    Rv=set(inverse(R))
    R=set(R)
    R=(R-(R&Rv))|(Ix&R)
    return R

#Un=1，mR^n是传递关系
def transitiverelation(X,R):
    n=len(X)
    Rn=R
    for k in range(2,n):
        Rn=set(Rn)| set(powern(R,k))
    return Rn

#自反关系判断
def isreflexiverelation(X,R):
    Ix=Ixset(X)
    tv=set(R)==(set(R)|set(Ix))
    return tv

#对称关系判断
def issymmetricrelation(X,R):
    Rv=inverse(R)
    tv=set(R)==set(Rv)
    return tv

#反对称关系判断
def isantisymmetricrelation(X,R):
    Ix=Ixset(X)
    Rv=inverse(R)
    tv=(set(R)&set(Rv))<=Ix
    return tv

#传递关系判断
def istransitiverelation(X,R):
    P2=powern(R,2)
    tv=P2<=R
    return tv

#自反闭包
def r(X,R):
    R=reflexiverelation(X,R)
    return R

#反自反闭包
def i(X,R):
    R=irreflexiverelation(X,R)
    return R

#对称闭包
def s(X,R):
    R=symmetricrelation(X,R)
    return R

#反对称闭包
def a(X,R):
    R=antisymmetricrelation(X,R)
    return R

#传递闭包
def t(X,R):
    R=transitiverelation(X,R)
    return R

#构建模关系
def modm(n,m):
    R=set({})
    for i in range(n):
        for j in range(n):
            if(i%m==j%m and i!=j):
                R=R|{(i,j)}
    return R

#判断是否为等价关系
def isequivalent(X,R):
    tv =isreflexive(X,R) and issymmetric(X,R) and istransitive (X,R)
    return tv

def isequivalentrelation(X,R):
    tv=isreflexiverelation(X,R) and issymmetricrelation(X,R) and istransitiverelation (X,R)
    return tv

#求等价类
def equivalentclass(X,R,x):
    Ec=set({})
    for (u,v) in R:
        if(x==u or x==v):
            Ec=Ec | set({u})| set({v})
    return Ec

#求商集
def quotientset(X,R):
    Qs=set({})
    for x in X:
        Ec=equivalentclass(X,R,x)
        Qs=Qs|{tuple(sorted(Ec))}
    return Qs

#将一种划分P构建为等价关系R
def partition2equivalent(P):
    R=set({})
    for p in P:
        for a in p:
            for b in p:
                R=R|{(a,b)}
    return R

#构建整除关系
def exactdivision(X):
    Ed=set({})
    for i in X:
        for j in X:
            if(i %j == 0):
                Ed=Ed|{(i,j)}
    return Ed

#判断是否为偏序关系
def ispartialorder(X,R):
    tv=isreflexive(X,R) and isantisymmetric(X,R) and istransitive (X,R)
    return tv

#构建偏序集合
def powerparset(R):
    global Ps
    Ps=set({})
    for a in R:
        for b in R:
            if(set(a)<=set(b)):
                Ps=Ps|{(b,a)}
    return Ps

#哈斯图化简
def HasseDiagram(X,R):
    R1=R
    for (u,v) in R:
        if(u ==v):
            R1=R1-{(u,v)}
    R=R1
    for (x,y)in R:
        for (u,v) in R:
            if(y == u and (x,v) in R1):
                R1=R1-{(x,v)}
    return R1

#构建偏序集合
def powerindexparset(R):
    global Ps
    R=sorted(R)
    Ps=set({})
    for a in R:
        for b in R:
            if(set(a)<=set(b)):
                Ps=Ps|{(R.index(b),R.index(a))}
    return Ps

#构建拟序集合
def powerindexquasiorder(R):
    global Pq
    R=sorted(R)
    Pq=set({})
    for a in R:
        for b in R:
            if(set(a)<set(b)):
                Pq=Pq|{(R.index(b),R.index(a))}
    return Pq

#全序集判断
def istotalorder(X,R):
    tv=ispartialorder(X,R)
    for x in X:
        for y in X:
            tv=(x,y)in R or (y,x) in R
    return tv

#构建小于关系全序集
def totalorder(X):
    R=set({})
    for x in X:
        for y in X:
            if x<=y:
                R=R|{(x,y)}
    return R
    